#include "pbalgorithm.h"
#include "../utils/utils.h"
#include "../os/platform.h"
#include "../utils/fastsort.h"

#include <stdlib.h>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

//
// BIG
//

struct BIG
{
    BIG(int value) { a = value; }

    uint32_t a;                             // "a" alapjan rendezi SMALL-et
    uint8_t buff[1024-sizeof(uint32_t)];

    friend bool operator<(const BIG &obj1, const BIG &obj2);
};

bool operator<(const BIG &obj1, const BIG &obj2)
{
    return obj1.a < obj2.a;
}

//
// SMALL
//

struct SMALL
{
    SMALL(int value) { a = value; }

    uint32_t a;                             // "a" alapjan rendezi SMALL-t
    uint8_t buff[16-sizeof(uint32_t)];

    friend bool operator<(const SMALL &obj1, const SMALL &obj2);
};

bool operator<(const SMALL &obj1, const SMALL &obj2)
{
    return obj1.a < obj2.a;
}

// a functor gyorsabb, mint a fuggveny :)
struct SmallLessFunctor
{
    bool operator() (SMALL *p, SMALL *q) { return p->a < q->a; }
} SmallLess;


// debug

void printx(const SMALL *a, int max)
{
    for (int i=0; i<max; i++)
        printf("%2d. %d\n", i, a[i].a);
}

void printptrx(SMALL **a, int max)
{
    for (int i=0; i<max; i++)
        printf("%2d. %d\n", i, a[i]->a);
}


//
// vector helper -ek 
//

template<class T>
void Vector(int count, int size, IResultWriter *results, const char *type)
{
    vector<T> vec;
    vec.reserve(size);

    double start, end;
    char buff[128];

    start = os_GetTime();

    for (int c=0; c<count; c++)
    {
        vec.clear();                    // ez mennyit visz el az idobol vajon?
        for (int i=0; i<size; i++)
            vec.push_back(T(i));
    }

    end = os_GetTime();

    sprintf(buff, "vector.push_back<%s>%dx%d", type, count, size);
    results->WriteNode(buff, (float)(end - start));
}


template<class T>
static void VectorSort(int size, IResultWriter *results, const char *type)
{
    vector<T> vec;
    vec.reserve(size);

    // veletlen
    for (int i=0; i<size; i++)
        vec.push_back((uint32_t)rand());

    double start = os_GetTime();     
    sort(vec.begin(), vec.end());
    double end = os_GetTime();

    char buff[128];
    sprintf(buff, "rnd_sortvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // novekvo
    for (int i=0; i<size; i++)
        vec[i] = i;

    start = os_GetTime();     
    sort(vec.begin(), vec.end());
    end = os_GetTime();

    sprintf(buff, "asc_sortvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // csokkeno 

    for (int i=0; i<size; i++)
        vec[i] = size - i;

    start = os_GetTime();     
    sort(vec.begin(), vec.end());
    end = os_GetTime();

    sprintf(buff, "desc_sortvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));
}


template<class T>
static void VectorSortPtr(int size, IResultWriter *results, const char *type)
{
    vector<T*> vec;
    vec.reserve(size);

    // veletlen
    for (int i=0; i<size; i++)
        vec.push_back(new T((uint32_t)rand()));

    
    double start = os_GetTime();     
    sort(vec.begin(), vec.end(), SmallLess);
    double end = os_GetTime();

    char buff[128];
    sprintf(buff, "rnd_sortptrvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // novekvo
    for (int i=0; i<size; i++)
    {
        delete vec[i];
        vec[i] = new T(i);
    }

    start = os_GetTime();     
    sort(vec.begin(), vec.end(), SmallLess);
    end = os_GetTime();

    sprintf(buff, "asc_sortptrvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // csokkeno 

    for (int i=0; i<size; i++)
    {
        delete vec[i];
        vec[i] = new T(size - i);
    }

    start = os_GetTime();     
    sort(vec.begin(), vec.end(), SmallLess);
    end = os_GetTime();

    sprintf(buff, "desc_sortptrvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    for (int i=0; i<size; i++)
        delete vec[i];
}


template<class T>
static void MySort(int size, IResultWriter *results, const char *type)
{
    vector<T> vec;
    vec.reserve(size);

    // veletlen
    for (int i=0; i<size; i++)
        vec.push_back((uint32_t)rand());

    double start = os_GetTime();     
    FastSort(&vec[0], 0, (int)vec.size() - 1);
    double end = os_GetTime();

    char buff[128];
    sprintf(buff, "rnd_mysort<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // novekvo
    for (int i=0; i<size; i++)
        vec[i] = i;

    start = os_GetTime();     
    FastSort(&vec[0], 0, (int)vec.size() - 1);
    end = os_GetTime();

    sprintf(buff, "asc_mysort<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // csokkeno 

    for (int i=0; i<size; i++)
        vec[i] = size - i;

    start = os_GetTime();     
    FastSort(&vec[0], 0, (int)vec.size() - 1);
    end = os_GetTime();

    sprintf(buff, "desc_mysort<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));
}


template<class T>
static void MySortPtr(int size, IResultWriter *results, const char *type)
{
    vector<T*> vec;
    vec.reserve(size);

    // veletlen
    for (int i=0; i<size; i++)
        vec.push_back(new T((uint32_t)rand()));

    double start = os_GetTime();     
    FastSortPtr(&vec[0], 0, size-1);    
    double end = os_GetTime();

    char buff[128];
    sprintf(buff, "rnd_mysortptrvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // novekvo
    for (int i=0; i<size; i++)
    {
        delete vec[i];
        vec[i] = new T(i);
    }

    start = os_GetTime();     
    FastSortPtr(&vec[0], 0, size-1);
    end = os_GetTime();

    sprintf(buff, "asc_mysortptrvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    // csokkeno 

    for (int i=0; i<size; i++)
    {
        delete vec[i];
        vec[i] = new T(size - i);
    }

    start = os_GetTime();     
    FastSortPtr(&vec[0], 0, size-1);
    end = os_GetTime();

    sprintf(buff, "desc_mysortptrvector<%s>%d", type, size);
    results->WriteNode(buff, (float)(end - start));

    for (int i=0; i<size; i++)
        delete vec[i];
}


int qsort_cmpfunc(const void *p, const void *q)
{
    return ((const SMALL*)p)->a - ((const SMALL*)q)->a;
}

int qsortptr_cmpfunc(const void *p, const void *q)
{
    return (*(const SMALL**)p)->a - (*(const SMALL**)q)->a;
}


static void QSort(int size, IResultWriter *results)
{
    SMALL *vec = (SMALL*)malloc(sizeof(SMALL) * size);

    if (!vec)
        return ;

    // veletlen
    for (int i=0; i<size; i++)
        vec[i] = rand();

    double start = os_GetTime();     
    qsort(vec, size, sizeof(SMALL), qsort_cmpfunc);
    double end = os_GetTime();

    char buff[128];
    sprintf(buff, "rnd_qsortvector%d", size);
    results->WriteNode(buff, (float)(end - start));

    // novekvo
    for (int i=0; i<size; i++)
        vec[i] = i;

    start = os_GetTime();     
    qsort(vec, size, sizeof(SMALL), qsort_cmpfunc);
    end = os_GetTime();

    sprintf(buff, "asc_qsortvector%d", size);
    results->WriteNode(buff, (float)(end - start));

    // csokkeno 

    for (int i=0; i<size; i++)
        vec[i] = size - i;

    start = os_GetTime();     
    qsort(vec, size, sizeof(SMALL), qsort_cmpfunc);
    end = os_GetTime();

    sprintf(buff, "desc_qsortvector%d", size);
    results->WriteNode(buff, (float)(end - start));
}


static void QSortPtr(int size, IResultWriter *results)
{
    SMALL **vec = (SMALL**)malloc(sizeof(SMALL*) * size);

    if (!vec)
        return ;

    // veletlen
    for (int i=0; i<size; i++)
        vec[i] = new SMALL(rand());

    double start = os_GetTime();     
    qsort(vec, size, sizeof(SMALL*), qsortptr_cmpfunc);
    double end = os_GetTime();

    char buff[128];
    sprintf(buff, "rnd_qsortptrvector%d", size);
    results->WriteNode(buff, (float)(end - start));

    // novekvo
    for (int i=0; i<size; i++)
    {
        delete vec[i];
        vec[i] = new SMALL(i);
    }

    start = os_GetTime();     
    qsort(vec, size, sizeof(SMALL*), qsortptr_cmpfunc);
    end = os_GetTime();

    sprintf(buff, "asc_qsortptrvector%d", size);
    results->WriteNode(buff, (float)(end - start));

    // csokkeno 

    for (int i=0; i<size; i++)
    {
        delete vec[i];
        vec[i] = new SMALL(size - i);
    }

    start = os_GetTime();     
    qsort(vec, size, sizeof(SMALL*), qsortptr_cmpfunc);
    end = os_GetTime();

    sprintf(buff, "desc_qsortptrvector%d", size);
    results->WriteNode(buff, (float)(end - start));

    for (int i=0; i<size; i++)
        delete vec[i];
}

//
// list
//

static void List(int count, int size, IResultWriter *results)
{
    list<void*> l;

    double start, time_clear = 0, time_add = 0, time_iterate = 0;

    for (int c=0; c<count; c++)
    {        
        // add
        start = os_GetTime();

        for (int i=0; i<size; i++)
            l.push_back((void*)i);

        time_add += os_GetTime() - start;

        // iterate
        start = os_GetTime();
        int sum = 0;
        for (list<void*>::const_iterator it = l.begin(); it != l.end(); ++it)
            sum += (int)(*it);

        time_iterate += os_GetTime() - start;

        // clear vagy remove
        start = os_GetTime();
        l.clear();
        time_clear += os_GetTime() - start;
    }

    results->WriteNode(ft("list.push_back<void*>%dx%d", count, size), (float)time_add);
    results->WriteNode(ft("list_iter<void*>%dx%d", count, size), (float)time_iterate);
    results->WriteNode(ft("list.clear<void*>%dx%d", count, size), (float)time_clear);    
}

//
// map
//

static void Map(int size, IResultWriter *results)
{                      
    map<int, int> m;

    double start = os_GetTime();
    
    for (int i=0; i<size; i++)
        ++m[rand()];

    double end = os_GetTime();

    results->WriteNode(ft("++map[rnd]<int,int>%d", size), (float)(end-start));

    start = os_GetTime();
    volatile int hits = 0;    

    for (int i=0; i<size; i++)
    {         
        if (m.find(rand()) == m.end())
            ++hits;                             // nehogy leoptipalizalja az egesz ciklust...
    }

    end = os_GetTime();

    results->WriteNode(ft("map.find<int,int>%d", size), (float)(end-start));
}


//---------------------------------------------------------------------------------

void CAlgorithmBenchmark::Run(IResultWriter *results, const CCmdlineArgs *args)
{
    srand((int)(os_GetTime() * 1000));

    Vector<uint32_t>(10000, 1024, results, "uint32_t");
    Vector<uint32_t>(1000, 10240, results, "uint32_t");
    Vector<void*>(10000, 1024, results, "void*");
    Vector<void*>(1000, 10240, results, "void*");

    VectorSort<uint32_t>(102400, results, "uint32_t");

    VectorSort<BIG>(10240, results, "BIG");
    MySort<BIG>(10240, results, "BIG");

    VectorSort<SMALL>(102400, results, "SMALL");    
    MySort<SMALL>(102400, results, "SMALL");
    QSort(102400, results);

    VectorSortPtr<SMALL>(102400, results, "SMALL*");
    MySortPtr<SMALL>(102400, results, "SMALL*");
    QSortPtr(102400, results);            

    List(16, 10240, results);
    Map(102400, results);
}

